// @algorithm @lc id=100314 lang=cpp
// @title cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof

#include "algm/algm.h"
#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std;
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    // @test([3,9,20,null,null,15,7])=[[3],[20,9],[15,7]]
    // @test([3,9,20,null,null,15,7])=[[3],[20,9],[15,7]]
public:
    vector<vector<int>> levelOrder(TreeNode *root) {
        if (root == nullptr) {
            return {};
        }
        vector<vector<int>> ans;
        queue<vector<TreeNode *>> q;
        bool isOdd = true;
        q.push({root});
        while (!q.empty()) {
            vector<TreeNode *> temp = q.front();
            vector<TreeNode *> nextRow;
            q.pop();
            vector<int> row;
            // 奇数行
            if (isOdd) {
                for (auto &node : temp) {
                    row.push_back(node->val);
                    if (node->left) {
                        nextRow.push_back(node->left);
                    }
                    if (node->right) {
                        nextRow.push_back(node->right);
                    }
                }
            }
            // 偶数行
            else {
                for (auto &node : temp) {
                    row.push_back(node->val);
                    if (node->right) {
                        nextRow.push_back(node->right);
                    }
                    if (node->left) {
                        nextRow.push_back(node->left);
                    }
                }
            }
            isOdd = !isOdd;
            reverse(nextRow.begin(), nextRow.end());
            ans.push_back(row);
            if (!nextRow.empty()) {
                q.push(nextRow);
            }
        }
        return ans;
    }
};